class Solution {
public:
    int maximumGap(vector<int>& nums) {
        
        int n=nums.size();
        if(n<2){
            return 0;
        }
        int nMax=*max_element(nums.begin(),nums.end());
        int nMin=*min_element(nums.begin(),nums.end());
        int nMaxD=max(1,(nMax-nMin)/(n-1));
        int bucketSize=(nMax-nMin)/nMaxD+1;
        vector<pair<int,int>> vecBucket(bucketSize,{-1,-1});
        for(int i=0;i<nums.size();++i){
            int idx=(nums[i]-nMin)/nMaxD;
           // cout<<idx<<' '<<nMaxD<<endl;
            if(vecBucket[idx].first==-1){
                vecBucket[idx].first=vecBucket[idx].second=nums[i];
            }
            else{
                vecBucket[idx].first=min(vecBucket[idx].first,nums[i]);
                vecBucket[idx].second=max(vecBucket[idx].second,nums[i]);  
            }
        }
        int pre=-1;
        int nRet=0;
        for(int i=0;i<bucketSize;++i){
            if(vecBucket[i].first==-1){
                continue;
            }
            if(pre!=-1){
                nRet=max(nRet,vecBucket[i].first-vecBucket[pre].second);
            }
            pre=i;
        }
        return nRet;
    }
};
